package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.ListNode;
import kyssion.leetcode.util.ShowUtil;

public class code147_对链表进行插入排序 {

    public static void main(String[] args) {
        ListNode listNode = new code147_对链表进行插入排序()
                .insertionSortList(
                        ListNode.createListNode(
                                new int[]{
                                        3
                                }
                        )
                );
        ShowUtil.showNode(listNode);
    }

    public ListNode insertionSortList(ListNode head) {
        ListNode itemBefore;
        ListNode item;
        ListNode next;
        ListNode start = new ListNode(-1);
        ListNode end = start;
        start.next = head;
        itemBefore = start;
        while (head != null) {
            item = head;
            next = head;
            ListNode nextBefore = itemBefore;
            while (next != null) {
                if (next.val < item.val) {
                    item = next;
                    itemBefore = nextBefore;
                }
                next = next.next;
                nextBefore = nextBefore.next;
            }
            itemBefore.next = item.next;
            item.next = end.next;
            end.next = item;
            end = item;
            itemBefore = end;
            head = end.next;

        }
        return start.next;
    }

    public ListNode insertionSortList2(ListNode head) {
        if (head == null) return null;
        ListNode temp = new ListNode(0);
        temp.next = head;
        while (head.next != null) {
            if (head.val < head.next.val) {
                head = head.next;
                continue;
            }
            ListNode pre = temp;
            while (pre.next.val < head.next.val) {
                pre = pre.next;
            }
            ListNode cur = head.next;
            head.next = cur.next;
            cur.next = pre.next;
            pre.next = cur;

        }
        return temp.next;

    }
}
